Partition Array Into Two Arrays to Minimize Sum Difference
Let's solve the Partition Array Into Two Arrays to Minimize Sum Difference problem using Dynamic Programming.
Statement#
Suppose you are given an array, nums, containing positive numbers. You need to partition the array into two arrays such that the absolute difference between their sums is minimized.
Note: Each element of the
numsarray should be present in one of the partitioned arrays.
Let’s say you have the following array:
- [2, 3, 1]
The two partitioned arrays with the minimum difference in their sums are:
So, the minimum difference becomes .
Constraints:
-
nums.length -
nums[i]
Examples#
No. | nums | partitioned arrays | mimimum difference |
1 | [5, 4, 4, 7, 2, 9 ] | [4, 5, 7], [2, 4, 9] | 1 |
2 | [3, 25, 4, 12, 2] | [25], [12, 4, 3, 2] | 4 |
3 | [3, 7, 4, 12, 2] | [7, 4, 3], [12, 2] | 0 |
Try it yourself#
Implement your solution in the following playground.
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.
Solution#
We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.
Naive approach#
A naive approach is to generate all possible combinations of two arrays from the original array. We then check which combination minimizes the difference between the sums of the two partitioned arrays.
For example, we have the following array of values:
- nums:
To find the minimum difference, we try all possible combinations:
- Difference
- Difference
- Difference
- Difference
- Difference
- Difference
- Difference
- Difference
The calculation above shows that we need a recursive solution to make all possible combinations. In other words, we divide the problem into subproblems, and for each array element, we decide whether to place it in the first or second partitioned array. This is done using the following rules:
-
Base case: If we reach the end of the array, and there are no elements to add in either of the partitioned arrays, we return the absolute difference between the sums of the two arrays.
-
Otherwise, we calculate the difference in the sums of the two arrays for the two scenarios:
- add the current element to the first partitioned array
- add it to the second partitioned array
We then select the option that results in the minimum difference.
Let’s implement the algorithm as discussed above:
Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.
Time complexity#
The time complexity of the naive approach is , where is the total number of elements. This is because we have two possible choices for each element, either to include it in the first or the second partitioned array.
Space complexity#
Since we can’t have more than recursive calls on the call stack at any time, the space complexity of this approach is .
Optimized solution using dynamic programming#
Now, let’s improve the recursive solution using top-down and bottom-up approaches.
Top-down solution#
The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the recursive approach, the following three variables kept changing:
- The array index,
i. - The sum of the first partitioned array,
sum1. - The sum of the second partitioned array,
sum2.
We will use a 2-D table, dp with i rows, and sum1 + 1 columns to store the result, i.e., the difference between the sums of the partitioned arrays. We haven’t considered sum2 since, for a given i and sum1, sum2 of the remaining numbers will always be the same. At any later time, if we encounter the same subproblem, we can return the stored result from the table with an look-up instead of re-calculating that subproblem.
Let’s implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
As we avoided redundant calculations by storing all the intermediate results in a 2-D table, the time complexity of this approach is reduced to , where is the number of elements in the input array, and is the sum of all the elements.
Space complexity#
We now need space in memory to store intermediate values.
Bottom-up solution#
The bottom-up solution, also known as the Tabulation technique, is an iterative method of solving dynamic programming problems.
Suppose is the sum of all the elements in nums. Since we’re taking the absolute difference between the sums of the two partitioned arrays, our minimum difference will always be greater than or equal to . Therefore, to minimize the difference, each partitioned array must have a sum as close to as possible. To make things easier, we only need to ensure that the sum in one partitioned array is as close to as possible since, then, the remaining sum in the other partitioned array will also become as close to as possible.
We will initialize a 2-D table of size , where is the length of nums. This table will have the following properties:
-
Each row
irepresents the index we’re currently on. It ranges from to . -
Each column
srepresents the current sum we’re trying to achieve. It ranges from to .
We will iterate the table and fill it with either or depending on if the current sum s can be achieved from the available elements in the partitioned array or not. This is done based on the following rules:
- We exclude
nums[i]from the partitioned array and check whether the sumscan be formed from its previous elements.
if dp[i - 1][s]:
dp[i][s] = dp[i - 1][s]
- We include
nums[i]in the partitioned array and check whether the sumscan now be formed from its current elements.
elif s >= nums[i]:
dp[i][s] = dp[i - 1][s - nums[i]]
- If neither one of the above two conditions is true, the sum
scan not be formed usingnums[i]:
else:
dp[i][s] = 0
After the 2-D table has been filled completely, we will traverse its last row from right to left to find the sum closest to that the partitioned array can contain. Whenever we find an entry that is , the value of i at that entry will be the partitioned array sum. Using this sum we find the sum in the other partitioned array and then calculate their absolute difference.
Let’s look at the following illustration to get a better understanding of the solution:
1 of 23
2 of 23
3 of 23
4 of 23
5 of 23
6 of 23
7 of 23
8 of 23
9 of 23
10 of 23
11 of 23
12 of 23
13 of 23
14 of 23
15 of 23
16 of 23
17 of 23
18 of 23
19 of 23
20 of 23
21 of 23
22 of 23
23 of 23
Let’s implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
As we created a 2-D table to store the results of sub-problems that would be used later on, therefore, the time complexity of this approach will also be .
Space complexity#
We need space in memory to store the intermediate values.
Can we do better?#
You must have noticed in the above algorithm that to fill up a row, we only require the previous row’s values; that is, for filling the row against the element, we require the values from the previous row representing the element. Therefore, there is no point in storing the previous rows.
We can further improve this approach by using a lookup array of length instead of creating a table. Next, we update this array for each element using the same calculation which we used earlier.
The time complexity would remain the same, , because we still have to do the calculation for each element. The space complexity, however, reduces to since we are only maintaining an array of size .
Count of Subset Sum
Minimum Number of Refueling Stops